/**
 * @Author liangzai
 * @Description:
 */
public class BinaryTree {
    //时间复杂度O(n),字节面试题
    public int getMaxDepth3(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftlong = getMaxDepth3(root.left);
        if(leftlong < 0){
            return -1;
        }
        int rightlong = getMaxDepth3(root.right);
        if(rightlong < -1){
            return -1;
        }
        if(leftlong == -1 || rightlong == -1 || Math.abs(leftlong-rightlong)>=2){
            return -1;
        }else{
            return Math.max(leftlong,rightlong)+1;
        }
    }
    public boolean isBalanced2(TreeNode root) {
        if(root == null) return true;
        return getMaxDepth3(root) >= 0;
    }

    //二叉搜索树 转换为 双向链表
    static TreeNode prev = null;
    private void ConvertChild(TreeNode root){
        if(root == null){
            return ;
        }
        ConvertChild(root.left);
        root.left = prev;
        if(prev!=null){
            prev.right = root;
        }
        prev = root;
        ConvertChild(root.right);
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        ConvertChild(pRootOfTree);
        while(pRootOfTree.left != null){
            pRootOfTree = pRootOfTree.left;
        }
        return pRootOfTree;
    }

    //以前序遍历 创建一个二叉树
    private int i = 0;
    public TreeNode createTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            i++;
        }
        return root;
    }

    public void inOder(TreeNode root) {
        if (root == null) {
            return ;
        }
        inOder(root.left);
        System.out.print(root.val + " ");
        inOder(root.right);
    }
}
